// Created by WXX on 2021/9/12 10:28
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    static const int N = 35;
    int f[N][2];  // f[i][j]: 一共i位，且最高位是j对应的方案数

    int findIntegers(int n) {
        init();

        vector<int> nums;
        while (n) nums.push_back(n % 2), n /= 2;
        int res = 0;
        int last = 0;  // 前一位对应的值
        for (int i = nums.size() - 1; i >= 0; i--) {
            int x = nums[i];

            if (x) {
                res += f[i + 1][0];  // 当前为填写0对应的方案数
                if (last == 1) break;
            }
            last = x;

            if (!i) res++;
        }
        return res;
    }

    void init() {

        f[1][0] = f[1][1] = 1;

        for (int i = 2; i < N; i++) {
            f[i][0] += f[i - 1][0] + f[i - 1][1];
            f[i][1] += f[i - 1][0];
        }
    }
};

int main() {

    cout << Solution().findIntegers(5) << endl;  // 5
    cout << Solution().findIntegers(100) << endl;  // 34

    return 0;
}
